//
// Created by Jisam on 2024/8/17 21:44.
//
#include "template.h"
constexpr int MAXN = 10010;
using ll = long long;
struct node {
    int l, r;
    int max;
} segTree[MAXN * 3];

void build(int i, int l, int r) {
    segTree[i].l = l;
    segTree[i].r = r;
    segTree[i].max = 0;
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
}

void push_up(int i) {
    segTree[i].max = max(segTree[i << 1].max, segTree[(i << 1) | 1].max);
}

void update(int i, int k, int val) {
    if (segTree[i].l == k && segTree[i].r == k) {
        segTree[i].max = val;
        return;
    }
    int mid = (segTree[i].l + segTree[i].r) / 2;
    if (k <= mid) {
        update(i << 1, k, val);
    } else {
        update((i << 1) | 1, k, val);
    }
    push_up(i);
}

int query(int i, int l, int r) {
    if (segTree[i].l == l && segTree[i].r == r)
        return segTree[i].max;
    int mid = (segTree[i].l + segTree[i].r) / 2;
    if (r <= mid)return query(i << 1, l, r);
    else if (l > mid)return query((i << 1) | 1, l, r);
    else return max(query(i << 1, l, mid), query((i << 1) | 1, mid + 1, r));
}